package com.arrays.a2;

import java.util.*;
/*
三数之和
排序+双指针
 */
public class ThreeSum {

    /*
    解法1 排序+双指针
     */
    public static List<List<Integer>> threeSum1(int[] nums){
        List<List<Integer>> res=new ArrayList<>();
        Arrays.sort(nums);
        int len=nums.length;
        for (int i = 0; i < len-2; i++) {
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int start=i+1;
            int end=len-1;
            while (start<end) {
                if (nums[i] + nums[start] + nums[end] == 0) {
                    res.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    start++;
                    end--;
                    while (start<end&&nums[start]==nums[start-1]){
                        start++;
                    }
                    while (start<end&&nums[end]==nums[end+1]){
                        end--;
                    }
                } else if (nums[i] + nums[start] + nums[end] < 0) {
                    start++;
                } else {
                    end--;
                }

            }
        }
        return  res;
    }
    //1优化
    public List<List<Integer>> threeSum1_1(int[] nums) {
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<>(len);
        Arrays.sort(nums);
        //测试集合长度小于3 或 排序后 最大值<0 直接返回空集合
        if(len<3||nums[len-1]<0){
            return res;
        }
        for (int i = 0; i < len-2; i++) {
            if(nums[i]>0){
                break; // 最小值大于0直接跳出
            }
            if (i>0&&nums[i]==nums[i-1]){//去重
                continue;
            }
            int l=i+1;
            int r=len-1;
            while (l<r) {
                int sum=nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                    //缩小范围
                    l++;
                    r--;
                    while (l<r&&nums[l]==nums[l-1]){
                        l++;//去重
                    }
                    while (l<r&&nums[r]==nums[r+1]){
                        r--;//去重
                    }

                } else if (sum < 0) {
                    l++;
                } else {
                    r--;
                }

            }
        }
        return  res;

    }

    /*
    解法1 排序+双指针
        先预先算两数

     */
    public static List<List<Integer>> threeSum2(int[] nums){
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<>(len);
        Arrays.sort(nums);
        if(len<3||nums[0]>0||nums[len-1]<0){
            return res;
        }
        for (int i = 0; i < len-2; i++) {
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            int target=0-nums[i];
            int start=i+1;
            int end=len-1;
            while (start<end){
                int sum=nums[start]+nums[end];
                if (sum==target){
                    res.add(Arrays.asList(nums[i],nums[start],nums[end]));
                    start++;
                    end--;
                    while (start<end&&nums[start]==nums[start-1]){
                        start++;
                    }
                    while (start<end&&nums[end]==nums[end+1]){
                        end--;
                    }
                }else if (sum<target){
                    start++;
                }else {
                    end--;
                }

            }
        }
        return  res;
    }


    public static List<List<Integer>> threeSum3(int[] nums){
        Set<List<Integer>> res = new HashSet<>();
        int len=nums.length;
        Arrays.sort(nums);
        for (int i = 0; i < len-2; i++) {
            int l=i+1;
            int r=len-1;
            while (l<r){
                if (nums[i]+nums[l]+nums[r]==0){
                    res.add(Arrays.asList(nums[i],nums[l],nums[r]));
                    l++;
                    r--;
                }else if (nums[i]+nums[l]+nums[r]<0){
                    l++;
                }else {
                    r--;
                }
            }
        }
        ArrayList<List<Integer>> ans = new ArrayList<>();
        ans.addAll(res);

        return ans;
    }

    public static void main(String[] args) {
        int[] b={-1,0,1,2,-1,-4};
        List<List<Integer>> res2 = threeSum2(b);
        System.out.println(res2);

    }
}
